前端与编译原理：用 JS 写一个 JS 解释器

（给前端大全加星标，提升前端技能）

作者：jrainlau

https://segmentfault.com/a/1190000017241258

说起编译原理，印象往往只停留在本科时那些枯燥的课程和晦涩的概念。作为前端开发者，编译原理似乎离我们很远，对它的理解很可能仅仅局限于“抽象语法树（AST）”。但这仅仅是个开头而已。编译原理的使用，甚至能让我们利用JS直接写一个能运行JS代码的解释器。

项目地址：https://github.com/jrainlau/canjs

在线体验：https://codepen.io/jrainlau/pen/YRgQXo

一、为什么要用JS写JS的解释器

接触过小程序开发的同学应该知道，小程序运行的环境禁止 newFunction， eval等方法的使用，导致我们无法直接执行字符串形式的动态代码。此外，许多平台也对这些JS自带的可执行动态代码的方法进行了限制，那么我们是没有任何办法了吗？既然如此，我们便可以用JS写一个解析器，让JS自己去运行自己。

在开始之前，我们先简单回顾一下编译原理的一些概念。

二、什么是编译器

说到编译原理，肯定离不开编译器。简单来说，当一段代码经过编译器的词法分析、语法分析等阶段之后，会生成一个树状结构的“抽象语法树（AST）”，该语法树的每一个节点都对应着代码当中不同含义的片段。

比如有这么一段代码：

1. const a = 1

2. console.log(a)

经过编译器处理后，它的AST长这样：

1. {

2.  "type": "Program",

3.  "start": 0,

4.  "end": 26,

5.  "body": [

6.    {

7.      "type": "VariableDeclaration",

8.      "start": 0,

9.      "end": 11,

10.      "declarations": [

11.        {

12.          "type": "VariableDeclarator",

13.          "start": 6,

14.          "end": 11,

15.          "id": {

16.            "type": "Identifier",

17.            "start": 6,

18.            "end": 7,

19.            "name": "a"

20.          },

21.          "init": {

22.            "type": "Literal",

23.            "start": 10,

24.            "end": 11,

25.            "value": 1,

26.            "raw": "1"

27.          }

28.        }

29.      ],

30.      "kind": "const"

31.    },

32.    {

33.      "type": "ExpressionStatement",

34.      "start": 12,

35.      "end": 26,

36.      "expression": {

37.        "type": "CallExpression",

38.        "start": 12,

39.        "end": 26,

40.        "callee": {

41.          "type": "MemberExpression",

42.          "start": 12,

43.          "end": 23,

44.          "object": {

45.            "type": "Identifier",

46.            "start": 12,

47.            "end": 19,

48.            "name": "console"

49.          },

50.          "property": {

51.            "type": "Identifier",

52.            "start": 20,

53.            "end": 23,

54.            "name": "log"

55.          },

56.          "computed": false

57.        },

58.        "arguments": [

59.          {

60.            "type": "Identifier",

61.            "start": 24,

62.            "end": 25,

63.            "name": "a"

64.          }

65.        ]

66.      }

67.    }

68.  ],

69.  "sourceType": "module"

70. }

常见的JS编译器有 babylon， acorn等等，感兴趣的同学可以在 AST explorer 这个网站自行体验。

可以看到，编译出来的AST详细记录了代码中所有语义代码的类型、起始位置等信息。这段代码除了根节点 Program外，主体包含了两个节点 VariableDeclaration和 ExpressionStatement，而这些节点里面又包含了不同的子节点。

正是由于AST详细记录了代码的语义化信息，所以Babel，Webpack，Sass，Less等工具可以针对代码进行非常智能的处理。

三、什么是解释器

如同翻译人员不仅能看懂一门外语，也能对其艺术加工后把它翻译成母语一样，人们把能够将代码转化成AST的工具叫做“编译器”，而把能够将AST翻译成目标语言并运行的工具叫做“解释器”。

在编译原理的课程中，我们思考过这么一个问题：如何让计算机运行算数表达式 1+2+3：

1. 1 + 2 + 3

当机器执行的时候，它可能会是这样的机器码：

1. 1 PUSH 1

2. 2 PUSH 2

3. 3 ADD

4. 4 PUSH 3

5. 5 ADD

而运行这段机器码的程序，就是解释器。

在这篇文章中，我们不会搞出机器码这样复杂的东西，仅仅是使用JS在其runtime环境下去解释JS代码的AST。由于解释器使用JS编写，所以我们可以大胆使用JS自身的语言特性，比如this绑定、new关键字等等，完全不需要对它们进行额外处理，也因此让JS解释器的实现变得非常简单。

在回顾了编译原理的基本概念之后，我们就可以着手进行开发了。

四、节点遍历器

通过分析上文的AST，可以看到每一个节点都会有一个类型属性 type，不同类型的节点需要不同的处理方式，处理这些节点的程序，就是“节点处理器 nodeHandler”。

定义一个节点处理器：

1. const nodeHandler = {

2.  Program () {},

3.  VariableDeclaration () {},

4.  ExpressionStatement () {},

5.  MemberExpression () {},

6.  CallExpression () {},

7.  Identifier () {}

8. }

关于节点处理器的具体实现，会在后文进行详细探讨，这里暂时不作展开。

有了节点处理器，我们便需要去遍历AST当中的每一个节点，递归地调用节点处理器，直到完成对整棵语法书的处理。

定义一个节点遍历器 NodeIterator：

1. class NodeIterator {

2.  constructor (node) {

3.    this.node = node

4.    this.nodeHandler = nodeHandler

5.  }

6.  traverse (node) {

7.    // 根据节点类型找到节点处理器当中对应的函数

8.    const _eval = this.nodeHandler[node.type]

9.    // 若找不到则报错

10.    if (!_eval) {

11.      throw new Error(`canjs: Unknown node type "${node.type}".`)

12.    }

13.    // 运行处理函数

14.    return _eval(node)

15.  }

16. }

理论上，节点遍历器这样设计就可以了，但仔细推敲，发现漏了一个很重要的东西——作用域处理。

回到节点处理器的 VariableDeclaration()方法，它用来处理诸如 consta=1这样的变量声明节点。假设它的代码如下：

1.  VariableDeclaration (node) {

2.    for (const declaration of node.declarations) {

3.      const { name } = declaration.id

4.      const value = declaration.init ? traverse(declaration.init) : undefined

5.      // 问题来了，拿到了变量的名称和值，然后把它保存到哪里去呢？

6.      // ...

7.    }

8.  },

问题在于，处理完变量声明节点以后，理应把这个变量保存起来。按照JS语言特性，这个变量应该存放在一个作用域当中。在JS解析器的实现过程中，这个作用域可以被定义为一个 scope对象。

改写节点遍历器，为其新增一个 scope对象：

1. class NodeIterator {

2.  constructor (node, scope = {}) {

3.    this.node = node

4.    this.scope = scope

5.    this.nodeHandler = nodeHandler

6.  }

7.  traverse (node, options = {}) {

8.    const scope = options.scope || this.scope

9.    const nodeIterator = new NodeIterator(node, scope)

10.    const _eval = this.nodeHandler[node.type]

11.    if (!_eval) {

12.      throw new Error(`canjs: Unknown node type "${node.type}".`)

13.    }

14.    return _eval(nodeIterator)

15.  }

16.  createScope (blockType = 'block') {

17.    return new Scope(blockType, this.scope)

18.  }

19. }

然后节点处理函数 VariableDeclaration()就可以通过 scope保存变量了：

1.  VariableDeclaration (nodeIterator) {

2.    const kind = nodeIterator.node.kind

3.    for (const declaration of nodeIterator.node.declarations) {

4.      const { name } = declaration.id

5.      const value = declaration.init ? nodeIterator.traverse(declaration.init) : undefined

6.      // 在作用域当中定义变量

7.      // 如果当前是块级作用域且变量用var定义，则定义到父级作用域

8.      if (nodeIterator.scope.type === 'block' && kind === 'var') {

9.        nodeIterator.scope.parentScope.declare(name, value, kind)

10.      } else {

11.        nodeIterator.scope.declare(name, value, kind)

12.      }

13.    }

14.  },

关于作用域的处理，可以说是整个JS解释器最难的部分。接下来我们将对作用域处理进行深入的剖析。

五、作用域处理

考虑到这样一种情况：

1. const a = 1

2. {

3.  const b = 2

4.  console.log(a)

5. }

6. console.log(b)

运行结果必然是能够打印出 a的值，然后报错： UncaughtReferenceError:bisnotdefined。

这段代码就是涉及到了作用域的问题。块级作用域或者函数作用域可以读取其父级作用域当中的变量，反之则不行，所以对于作用域我们不能简单地定义一个空对象，而是要专门进行处理。

定义一个作用域基类 Scope：

1. class Scope {

2.  constructor (type, parentScope) {

3.    // 作用域类型，区分函数作用域function和块级作用域block

4.    this.type = type

5.    // 父级作用域

6.    this.parentScope = parentScope

7.    // 全局作用域

8.    this.globalDeclaration = standardMap

9.    // 当前作用域的变量空间

10.    this.declaration = Object.create(null)

11.  }

12.  /*

13.   * get/set方法用于获取/设置当前作用域中对应name的变量值

14.     符合JS语法规则，优先从当前作用域去找，若找不到则到父级作用域去找，然后到全局作用域找。

15.     如果都没有，就报错

16.   */

17.  get (name) {

18.    if (this.declaration[name]) {

19.      return this.declaration[name]

20.    } else if (this.parentScope) {

21.      return this.parentScope.get(name)

22.    } else if (this.globalDeclaration[name]) {

23.      return this.globalDeclaration[name]

24.    }

25.    throw new ReferenceError(`${name} is not defined`)

26.  }

27.  set (name, value) {

28.    if (this.declaration[name]) {

29.      this.declaration[name] = value

30.    } else if (this.parentScope[name]) {

31.      this.parentScope.set(name, value)

32.    } else {

33.      throw new ReferenceError(`${name} is not defined`)

34.    }

35.  }

36.  /**

37.   * 根据变量的kind调用不同的变量定义方法

38.   */

39.  declare (name, value, kind = 'var') {

40.    if (kind === 'var') {

41.      return this.varDeclare(name, value)

42.    } else if (kind === 'let') {

43.      return this.letDeclare(name, value)

44.    } else if (kind === 'const') {

45.      return this.constDeclare(name, value)

46.    } else {

47.      throw new Error(`canjs: Invalid Variable Declaration Kind of "${kind}"`)

48.    }

49.  }

50.  varDeclare (name, value) {

51.    let scope = this

52.    // 若当前作用域存在非函数类型的父级作用域时，就把变量定义到父级作用域

53.    while (scope.parentScope && scope.type !== 'function') {

54.      scope = scope.parentScope

55.    }

56.    this.declaration[name] = new SimpleValue(value, 'var')

57.    return this.declaration[name]

58.  }

59.  letDeclare (name, value) {

60.    // 不允许重复定义

61.    if (this.declaration[name]) {

62.      throw new SyntaxError(`Identifier ${name} has already been declared`)

63.    }

64.    this.declaration[name] = new SimpleValue(value, 'let')

65.    return this.declaration[name]

66.  }

67.  constDeclare (name, value) {

68.    // 不允许重复定义

69.    if (this.declaration[name]) {

70.      throw new SyntaxError(`Identifier ${name} has already been declared`)

71.    }

72.    this.declaration[name] = new SimpleValue(value, 'const')

73.    return this.declaration[name]

74.  }

75. }

这里使用了一个叫做 simpleValue()的函数来定义变量值，主要用于处理常量：

1. class SimpleValue {

2.  constructor (value, kind = '') {

3.    this.value = value

4.    this.kind = kind

5.  }

6.  set (value) {

7.    // 禁止重新对const类型变量赋值

8.    if (this.kind === 'const') {

9.      throw new TypeError('Assignment to constant variable')

10.    } else {

11.      this.value = value

12.    }

13.  }

14.  get () {

15.    return this.value

16.  }

17. }

处理作用域问题思路，关键的地方就是在于JS语言本身寻找变量的特性——优先当前作用域，父作用域次之，全局作用域最后。反过来，在节点处理函数 VariableDeclaration()里，如果遇到块级作用域且关键字为 var，则需要把这个变量也定义到父级作用域当中，这也就是我们常说的“全局变量污染”。

JS标准库注入

细心的读者会发现，在定义 Scope基类的时候，其全局作用域 globalScope被赋值了一个 standardMap对象，这个对象就是JS标准库。

简单来说，JS标准库就是JS这门语言本身所带有的一系列方法和属性，如常用的 setTimeout， console.log等等。为了让解析器也能够执行这些方法，所以我们需要为其注入标准库：

1. const standardMap = {

2.  console: new SimpleValue(console)

3. }

这样就相当于往解析器的全局作用域当中注入了 console这个对象，也就可以直接被使用了。

六、节点处理器

在处理完节点遍历器、作用域处理的工作之后，便可以来编写节点处理器了。顾名思义，节点处理器是专门用来处理AST节点的，上文反复提及的 VariableDeclaration()方法便是其中一个。下面将对部分关键的节点处理器进行讲解。

在开发节点处理器之前，需要用到一个工具，用于判断JS语句当中的 return， break， continue关键字。

关键字判断工具 Signal

定义一个 Signal基类：

1. class Signal {

2.  constructor (type, value) {

3.    this.type = type

4.    this.value = value

5.  }

6.  static Return (value) {

7.    return new Signal('return', value)

8.  }

9.  static Break (label = null) {

10.    return new Signal('break', label)

11.  }

12.  static Continue (label) {

13.    return new Signal('continue', label)

14.  }

15.  static isReturn(signal) {

16.    return signal instanceof Signal && signal.type === 'return'

17.  }

18.  static isContinue(signal) {

19.    return signal instanceof Signal && signal.type === 'continue'

20.  }

21.  static isBreak(signal) {

22.    return signal instanceof Signal && signal.type === 'break'

23.  }

24.  static isSignal (signal) {

25.    return signal instanceof Signal

26.  }

27. }

有了它，就可以对语句当中的关键字进行判断处理，接下来会有大用处。

1、变量定义节点处理器—— VariableDeclaration()

最常用的节点处理器之一，负责把变量注册到正确的作用域。

1.  VariableDeclaration (nodeIterator) {

2.    const kind = nodeIterator.node.kind

3.    for (const declaration of nodeIterator.node.declarations) {

4.      const { name } = declaration.id

5.      const value = declaration.init ? nodeIterator.traverse(declaration.init) : undefined

6.      // 在作用域当中定义变量

7.      // 若为块级作用域且关键字为var，则需要做全局污染

8.      if (nodeIterator.scope.type === 'block' && kind === 'var') {

9.        nodeIterator.scope.parentScope.declare(name, value, kind)

10.      } else {

11.        nodeIterator.scope.declare(name, value, kind)

12.      }

13.    }

14.  },

2、标识符节点处理器—— Identifier()

专门用于从作用域中获取标识符的值。

1.  Identifier (nodeIterator) {

2.    if (nodeIterator.node.name === 'undefined') {

3.      return undefined

4.    }

5.    return nodeIterator.scope.get(nodeIterator.node.name).value

6.  },

3、字符节点处理器—— Literal()

返回字符节点的值。

1.  Literal (nodeIterator) {

2.    return nodeIterator.node.value

3.  }

4、表达式调用节点处理器—— CallExpression()

用于处理表达式调用节点的处理器，如处理 func()， console.log()等。

1.  CallExpression (nodeIterator) {

2.    // 遍历callee获取函数体

3.    const func = nodeIterator.traverse(nodeIterator.node.callee)

4.    // 获取参数

5.    const args = nodeIterator.node.arguments.map(arg => nodeIterator.traverse(arg))

6.    let value

7.    if (nodeIterator.node.callee.type === 'MemberExpression') {

8.      value = nodeIterator.traverse(nodeIterator.node.callee.object)

9.    }

10.    // 返回函数运行结果

11.    return func.apply(value, args)

12.  },

5、表达式节点处理器—— MemberExpression()

区分于上面的“表达式调用节点处理器”，表达式节点指的是 person.say， console.log这种函数表达式。

1.  MemberExpression (nodeIterator) {

2.    // 获取对象，如console

3.    const obj = nodeIterator.traverse(nodeIterator.node.object)

4.    // 获取对象的方法，如log

5.    const name = nodeIterator.node.property.name

6.    // 返回表达式，如console.log

7.    return obj[name]

8.  }

6、块级声明节点处理器—— BlockStatement()

非常常用的处理器，专门用于处理块级声明节点，如函数、循环、 try...catch...当中的情景。

1.  BlockStatement (nodeIterator) {

2.    // 先定义一个块级作用域

3.    let scope = nodeIterator.createScope('block')

4.    // 处理块级节点内的每一个节点

5.    for (const node of nodeIterator.node.body) {

6.      if (node.type === 'VariableDeclaration' && node.kind === 'var') {

7.        for (const declaration of node.declarations) {

8.          scope.declare(declaration.id.name, declaration.init.value, node.kind)

9.        }

10.      } else if (node.type === 'FunctionDeclaration') {

11.        nodeIterator.traverse(node, { scope })

12.      }

13.    }

14.    // 提取关键字（return, break, continue）

15.    for (const node of nodeIterator.node.body) {

16.      if (node.type === 'FunctionDeclaration') {

17.        continue

18.      }

19.      const signal = nodeIterator.traverse(node, { scope })

20.      if (Signal.isSignal(signal)) {

21.        return signal

22.      }

23.    }

24.  }

可以看到这个处理器里面有两个 for...of循环。第一个用于处理块级内语句，第二个专门用于识别关键字，如循环体内部的 break， continue或者函数体内部的 return。

7、函数定义节点处理器—— FunctionDeclaration()

往作用当中声明一个和函数名相同的变量，值为所定义的函数：

1.  FunctionDeclaration (nodeIterator) {

2.    const fn = NodeHandler.FunctionExpression(nodeIterator)

3.    nodeIterator.scope.varDeclare(nodeIterator.node.id.name, fn)

4.    return fn    

5.  }

8、函数表达式节点处理器—— FunctionExpression()

用于定义一个函数：

1.  FunctionExpression (nodeIterator) {

2.    const node = nodeIterator.node

3.    /**

4.     * 1、定义函数需要先为其定义一个函数作用域，且允许继承父级作用域

5.     * 2、注册`this`, `arguments`和形参到作用域的变量空间

6.     * 3、检查return关键字

7.     * 4、定义函数名和长度

8.     */

9.    const fn = function () {

10.      const scope = nodeIterator.createScope('function')

11.      scope.constDeclare('this', this)

12.      scope.constDeclare('arguments', arguments)

13.      node.params.forEach((param, index) => {

14.        const name = param.name

15.        scope.varDeclare(name, arguments[index])

16.      })

17.      const signal = nodeIterator.traverse(node.body, { scope })

18.      if (Signal.isReturn(signal)) {

19.        return signal.value

20.      }

21.    }

22.    Object.defineProperties(fn, {

23.      name: { value: node.id ? node.id.name : '' },

24.      length: { value: node.params.length }

25.    })

26.    return fn

27.  }

9、this表达式处理器—— ThisExpression()

该处理器直接使用JS语言自身的特性，把 this关键字从作用域中取出即可。

1.  ThisExpression (nodeIterator) {

2.    const value = nodeIterator.scope.get('this')

3.    return value ? value.value : null

4.  }

10、new表达式处理器—— NewExpression()

和 this表达式类似，也是直接沿用JS的语言特性，获取函数和参数之后，通过 bind关键字生成一个构造函数，并返回。

1.  NewExpression (nodeIterator) {

2.    const func = nodeIterator.traverse(nodeIterator.node.callee)

3.    const args = nodeIterator.node.arguments.map(arg => nodeIterator.traverse(arg))

4.    return new (func.bind(null, ...args))

5.  }

11、For循环节点处理器—— ForStatement()

For循环的三个参数对应着节点的 init， test， update属性，对着三个属性分别调用节点处理器处理，并放回JS原生的for循环当中即可。

1.  ForStatement (nodeIterator) {

2.    const node = nodeIterator.node

3.    let scope = nodeIterator.scope

4.    if (node.init && node.init.type === 'VariableDeclaration' && node.init.kind !== 'var') {

5.      scope = nodeIterator.createScope('block')

6.    }

7.    for (

8.      node.init && nodeIterator.traverse(node.init, { scope });

9.      node.test ? nodeIterator.traverse(node.test, { scope }) : true;

10.      node.update && nodeIterator.traverse(node.update, { scope })

11.    ) {

12.      const signal = nodeIterator.traverse(node.body, { scope })

13.      if (Signal.isBreak(signal)) {

14.        break

15.      } else if (Signal.isContinue(signal)) {

16.        continue

17.      } else if (Signal.isReturn(signal)) {

18.        return signal

19.      }

20.    }

21.  }

同理， for...in， while和 do...while循环也是类似的处理方式，这里不再赘述。

12、If声明节点处理器—— IfStatemtnt()

处理If语句，包括 if， if...else， if...elseif...else。

1.  IfStatement (nodeIterator) {

2.    if (nodeIterator.traverse(nodeIterator.node.test)) {

3.      return nodeIterator.traverse(nodeIterator.node.consequent)

4.    } else if (nodeIterator.node.alternate) {

5.      return nodeIterator.traverse(nodeIterator.node.alternate)

6.    }

7.  }

同理， switch语句、三目表达式也是类似的处理方式。

上面列出了几个比较重要的节点处理器，在es5当中还有很多节点需要处理，详细内容可以访 https://github.com/jrainlau/canjs/blob/master/src/es_versions/es5.js 一探究竟。

七、定义调用方式

经过了上面的所有步骤，解析器已经具备处理es5代码的能力，接下来就是对这些散装的内容进行组装，最终定义一个方便用户调用的办法。

1. const { Parser } = require('acorn')

2. const NodeIterator = require('./iterator')

3. const Scope = require('./scope')

4. class Canjs {

5.  constructor (code = '', extraDeclaration = {}) {

6.    this.code = code

7.    this.extraDeclaration = extraDeclaration

8.    this.ast = Parser.parse(code)

9.    this.nodeIterator = null

10.    this.init()

11.  }

12.  init () {

13.    // 定义全局作用域，该作用域类型为函数作用域

14.    const globalScope = new Scope('function')

15.    // 根据入参定义标准库之外的全局变量

16.    Object.keys(this.extraDeclaration).forEach((key) => {

17.      globalScope.addDeclaration(key, this.extraDeclaration[key])

18.    })

19.    this.nodeIterator = new NodeIterator(null, globalScope)

20.  }

21.  run () {

22.    return this.nodeIterator.traverse(this.ast)

23.  }

24. }

这里我们定义了一个名为 Canjs的基类，接受字符串形式的JS代码，同时可定义标准库之外的变量。当运行 run()方法的时候就可以得到运行结果。

八、后续

至此，整个JS解析器已经完成，可以很好地运行ES5的代码（可能还有bug没有发现）。但是在当前的实现中，所有的运行结果都是放在一个类似沙盒的地方，无法对外界产生影响。如果要把运行结果取出来，可能的办法有两种。第一种是传入一个全局的变量，把影响作用在这个全局变量当中，借助它把结果带出来；另外一种则是让解析器支持 export语法，能够把 export语句声明的结果返回，感兴趣的读者可以自行研究。

最后，这个JS解析器已经在我的Github上开源，欢迎前来交流：https://github.com/jrainlau/canjs

参考资料

• 从零开始写一个Javascript解析器

• 微信小程序也要强行热更代码，鹅厂不服你来肛我呀

• jkeylu/evil-eval

推荐阅读

（点击标题可跳转阅读）

觉得本文对你有帮助？请分享给更多人

关注「前端大全」加星标，提升前端技能